{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "bE6S_bHcuZIg"
   },
   "outputs": [],
   "source": [
    "##### Copyright 2021 The Cirq Developers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cellView": "form",
    "id": "fwpnM5i0uaRZ"
   },
   "outputs": [],
   "source": [
    "# @title Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "# you may not use this file except in compliance with the License.\n",
    "# You may obtain a copy of the License at\n",
    "#\n",
    "# https://www.apache.org/licenses/LICENSE-2.0\n",
    "#\n",
    "# Unless required by applicable law or agreed to in writing, software\n",
    "# distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "# See the License for the specific language governing permissions and\n",
    "# limitations under the License."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "AF-CFuvzPx4x"
   },
   "source": [
    "# Named Topologies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "b692fcab6e07"
   },
   "source": [
    "<table class=\"tfo-notebook-buttons\" align=\"left\">\n",
    "  <td>\n",
    "    <a target=\"_blank\" href=\"https://quantumai.google/cirq/named_topologies\"><img src=\"https://quantumai.google/site-assets/images/buttons/quantumai_logo_1x.png\" />View on QuantumAI</a>\n",
    "  </td>\n",
    "  <td>\n",
    "    <a target=\"_blank\" href=\"https://colab.research.google.com/github/quantumlib/Cirq/blob/main/docs/named_topologies.ipynb\"><img src=\"https://quantumai.google/site-assets/images/buttons/colab_logo_1x.png\" />Run in Google Colab</a>\n",
    "  </td>\n",
    "  <td>\n",
    "    <a target=\"_blank\" href=\"https://github.com/quantumlib/Cirq/blob/main/docs/named_topologies.ipynb\"><img src=\"https://quantumai.google/site-assets/images/buttons/github_logo_1x.png\" />View source on GitHub</a>\n",
    "  </td>\n",
    "  <td>\n",
    "    <a href=\"https://storage.googleapis.com/tensorflow_docs/Cirq/docs/named_topologies.ipynb\"><img src=\"https://quantumai.google/site-assets/images/buttons/download_icon_1x.png\" />Download notebook</a>\n",
    "  </td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "AXHWCnLzufVf"
   },
   "outputs": [],
   "source": [
    "try:\n",
    "    import cirq\n",
    "except ImportError:\n",
    "    print(\"installing cirq...\")\n",
    "    !pip install --quiet cirq\n",
    "    print(\"installed cirq.\")\n",
    "\n",
    "import cirq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "6zlksjAlum6f"
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "09358b36ef8d"
   },
   "source": [
    "## TiltedSquareLattice\n",
    "\n",
    "This is a grid lattice rotated 45-degrees.\n",
    "\n",
    "This topology is based on Google devices where plaquettes consist of four qubits in a square\n",
    "connected to a central qubit:\n",
    "\n",
    "    x   x\n",
    "      x\n",
    "    x   x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "6172a6b67648"
   },
   "outputs": [],
   "source": [
    "import itertools\n",
    "from cirq import TiltedSquareLattice\n",
    "\n",
    "side_lens = np.arange(1, 4 + 1)\n",
    "l = len(side_lens)\n",
    "\n",
    "fig, axes = plt.subplots(l, l, figsize=(3.5 * l, 3 * l))\n",
    "for widthi, heighti in itertools.product(np.arange(l), repeat=2):\n",
    "    width = side_lens[widthi]\n",
    "    height = side_lens[heighti]\n",
    "    ax = axes[heighti, widthi]\n",
    "    topo = TiltedSquareLattice(width, height)\n",
    "    topo.draw(ax=ax, tilted=False)\n",
    "\n",
    "    if widthi == 0:\n",
    "        ax.set_ylabel(f'Height {height}', fontsize=14)\n",
    "    if heighti == l - 1:\n",
    "        ax.set_xlabel(f'Width {width}', fontsize=14)\n",
    "\n",
    "    ax.set_title(f'n = {topo.n_nodes}', fontsize=14)\n",
    "\n",
    "fig.tight_layout()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "798f5800f37d"
   },
   "source": [
    "The corner nodes are not connected to each other. `width` and `height` refer to the rectangle\n",
    "formed by rotating the lattice 45 degrees. `width` and `height` are measured in half-unit\n",
    "cells, or equivalently half the number of central nodes.\n",
    "\n",
    "Nodes are 2-tuples of integers which may be negative. Please see `get_placements` for\n",
    "mapping this topology to a GridQubit Device."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "ad5780182be8"
   },
   "source": [
    "## Placement"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "6c977db39c1f"
   },
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "\n",
    "SYC23_GRAPH = nx.from_edgelist(\n",
    "    [\n",
    "        ((3, 2), (4, 2)),\n",
    "        ((4, 1), (5, 1)),\n",
    "        ((4, 2), (4, 1)),\n",
    "        ((4, 2), (4, 3)),\n",
    "        ((4, 2), (5, 2)),\n",
    "        ((4, 3), (5, 3)),\n",
    "        ((5, 1), (5, 0)),\n",
    "        ((5, 1), (5, 2)),\n",
    "        ((5, 1), (6, 1)),\n",
    "        ((5, 2), (5, 3)),\n",
    "        ((5, 2), (6, 2)),\n",
    "        ((5, 3), (5, 4)),\n",
    "        ((5, 3), (6, 3)),\n",
    "        ((5, 4), (6, 4)),\n",
    "        ((6, 1), (6, 2)),\n",
    "        ((6, 2), (6, 3)),\n",
    "        ((6, 2), (7, 2)),\n",
    "        ((6, 3), (6, 4)),\n",
    "        ((6, 3), (7, 3)),\n",
    "        ((6, 4), (6, 5)),\n",
    "        ((6, 4), (7, 4)),\n",
    "        ((6, 5), (7, 5)),\n",
    "        ((7, 2), (7, 3)),\n",
    "        ((7, 3), (7, 4)),\n",
    "        ((7, 3), (8, 3)),\n",
    "        ((7, 4), (7, 5)),\n",
    "        ((7, 4), (8, 4)),\n",
    "        ((7, 5), (7, 6)),\n",
    "        ((7, 5), (8, 5)),\n",
    "        ((8, 3), (8, 4)),\n",
    "        ((8, 4), (8, 5)),\n",
    "        ((8, 4), (9, 4)),\n",
    "    ]\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "ca39fc2f6773"
   },
   "source": [
    "You can manually generate mappings between `NamedTopology` nodes and device qubits using helper functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "0f6a1e57db87"
   },
   "outputs": [],
   "source": [
    "topo = TiltedSquareLattice(4, 2)\n",
    "\n",
    "cirq.draw_placements(\n",
    "    SYC23_GRAPH,\n",
    "    topo.graph,\n",
    "    [topo.nodes_to_gridqubits(offset=(3, 2)), topo.nodes_to_gridqubits(offset=(5, 3))],\n",
    "    tilted=False,\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "898879ebaf69"
   },
   "source": [
    "Or you can automatically generate placements using a subgraph monomorphism algorithm in NetworkX."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "de2d879d0111"
   },
   "outputs": [],
   "source": [
    "topo = TiltedSquareLattice(4, 2)\n",
    "placements = cirq.get_placements(SYC23_GRAPH, topo.graph)\n",
    "cirq.draw_placements(SYC23_GRAPH, topo.graph, placements[::3])\n",
    "print('...\\n')\n",
    "print(f'{len(placements)} total placements')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "44efeaf1c70e"
   },
   "source": [
    "## LineTopology\n",
    "\n",
    "This is a 1D linear topology.\n",
    "\n",
    "Node indices are contiguous integers starting from 0 with edges between\n",
    "adjacent integers.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "90d5b377b10c"
   },
   "outputs": [],
   "source": [
    "from cirq import LineTopology\n",
    "\n",
    "lens = np.arange(3, 12 + 1, 3)\n",
    "l = len(lens)\n",
    "fig, axes = plt.subplots(1, l, figsize=(3.5 * l, 3 * 1))\n",
    "\n",
    "for ax, n_nodes in zip(axes, lens):\n",
    "    LineTopology(n_nodes).draw(ax=ax, tilted=False)\n",
    "    ax.set_title(f'n =  {n_nodes}')\n",
    "\n",
    "fig.tight_layout()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "ffbdece786d1"
   },
   "source": [
    "### Manual placement"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "fb0f5289d6f5"
   },
   "outputs": [],
   "source": [
    "topo = LineTopology(9)\n",
    "\n",
    "cirq.draw_placements(\n",
    "    SYC23_GRAPH,\n",
    "    topo.graph,\n",
    "    [\n",
    "        {\n",
    "            i: q\n",
    "            for i, q in enumerate(\n",
    "                [\n",
    "                    cirq.GridQubit(4, 1),\n",
    "                    cirq.GridQubit(4, 2),\n",
    "                    cirq.GridQubit(5, 2),\n",
    "                    cirq.GridQubit(5, 3),\n",
    "                    cirq.GridQubit(6, 3),\n",
    "                    cirq.GridQubit(6, 4),\n",
    "                    cirq.GridQubit(7, 4),\n",
    "                    cirq.GridQubit(7, 5),\n",
    "                    cirq.GridQubit(8, 5),\n",
    "                ]\n",
    "            )\n",
    "        }\n",
    "    ],\n",
    "    tilted=False,\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "d3085236f6b7"
   },
   "source": [
    "### Automatic placement"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "47b899ba53dc"
   },
   "outputs": [],
   "source": [
    "topo = LineTopology(9)\n",
    "placements = cirq.get_placements(SYC23_GRAPH, topo.graph)\n",
    "cirq.draw_placements(SYC23_GRAPH, topo.graph, placements[::300])\n",
    "print('...\\n')\n",
    "print(f'{len(placements)} total placements')"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "named_topologies.ipynb",
   "toc_visible": true
  },
  "kernelspec": {
   "display_name": "Python 3",
   "name": "python3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
